public class sqrt {
    public static void main(String[] args) {
        System.out.println(sq(24));
        System.out.println(niu(24));
    }

    private static int niu(int x) {
        if(x==0){
            return 0;
        }

        return (int)sq2(x,x);

    }
//牛顿迭代
    private static double sq2(double i,int x) {
        double res = (i+x/i)/2;
        if(res==i){
            return i;
        }else {
            return sq2(res,x);
        }
    }
//二分查找
    private static int sq(int x) {
        int index=-1,l=0,r=x;
        while (l<=r) {
            int mid = (l + r) / 2;
            if (mid * mid <= x) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }
}
